#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
private:
    struct unit{
        int mask;
        int sides;
        unit(int mask_,int sides_):mask(mask_),sides(sides_){}
    };

    struct unitHash
    {
        size_t operator()(const unit& rhs) const {
            return hash<int>()(rhs.mask) ^ hash<int>()(rhs.sides);
        }
    };
    struct unitCmp
    {
        bool operator()(const unit& lhs, const unit& rhs) const {
            return lhs.mask == rhs.mask && lhs.sides == rhs.sides;
        }
    };

    bool makesquareCore(vector<int>& nums, unordered_map<unit,bool, unitHash, unitCmp>& memorys,int mask,int sides,int square_side) {
        unit memory_key(mask, sides);

        int total = 0;
        for (int i = 0; i < nums.size(); i++) {
            if((mask&(1<<i))==0)
                total += nums[i];
        }
        if (total > 0 && total % square_side == 0)
            ++sides;
        if (sides == 3)
            return true;
        auto it=memorys.find(memory_key);
        if (it != memorys.end())
            return it->second;
        bool res = false;
        int rem = (total / square_side + 1) * square_side - total;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]<= rem &&(mask & (1 << i)) > 1) {
                if (makesquareCore(nums, memorys, mask ^ (1 << i), sides, square_side)) {
                    res = true;
                    break;
                }
            }
        }
        memorys[memory_key] = res;
        return res;
        
    }
public:
    bool makesquare(vector<int>& nums) {
        if (nums.size() < 1)
            return false;
        int sum = 0;
        for (auto num : nums)
            sum += num;
        if (sum % 4 != 0)
            return false;
        int square_side = sum / 4;
        sort(nums.begin(), nums.end(),greater<int>());

        unordered_map<unit, bool, unitHash,unitCmp> memorys;
        return makesquareCore(nums, memorys, (1 << nums.size()) - 1, 0, square_side);
    }
};
//class Solution {
//private:
//    bool makesquareCore(vector<int>& nums, int index, vector<int>& state, int target) {
//        if (index == nums.size()) {
//            bool flag = true;
//            for (int i = 0; i < state.size(); ++i) {
//                if (state[i] != target) {
//                    flag = false;
//                    break;
//                }
//            }
//            return flag;
//        }
//        for (int i = 0; i < state.size(); ++i) {
//            if (state[i] + nums[index] <= target) {
//                state[i] += nums[index];
//                if (makesquareCore(nums, index + 1, state, target))
//                    return true;
//                state[i] -= nums[index];
//            }
//        }
//        return false;
//    }
//public:
//    bool makesquare(vector<int>& nums) {
//        if (nums.size() < 1)
//            return false;
//        int sum = 0;
//        for (auto num : nums)
//            sum += num;
//        if (sum % 4 != 0)
//            return false;
//        int side = sum / 4;
//        vector<int> state(4, 0);
//        sort(nums.begin(), nums.end(),greater<int>());
//        return makesquareCore(nums, 0, state, side);
//    }
//};